<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>全组合</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
        
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        <style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="全组合">全组合</h1>
<h1 id="1-78-subsets-不带有重复元素的全组合可能">1. 78 Subsets 不带有重复元素的全组合可能</h1>
<ul>
<li><a href="https://leetcode.com/problems/subsets/">https://leetcode.com/problems/subsets/</a></li>
</ul>
<p>Given a set of distinct integers, nums, return all possible subsets (the power set).</p>
<p>Note: The solution set must not contain duplicate subsets.</p>
<pre><code><code><div>Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
</div></code></code></pre>
<p>不容易想到的解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">subsets</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; List[List[int]]:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> nums:
            <span class="hljs-keyword">return</span> []

        res, cur = [[]], []
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(nums)):
            cur = [item + [nums[i]] <span class="hljs-keyword">for</span> item <span class="hljs-keyword">in</span> res]
            res += cur
            <span class="hljs-comment">#print(f"{i} {cur} {res}")</span>
        <span class="hljs-keyword">return</span> res
</div></code></pre>
<p>比较容易的想法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">subsets</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; List[List[int]]:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> nums:
            <span class="hljs-keyword">return</span> []
        
        ans = []
        <span class="hljs-comment"># nums.sort() 这一步可以不要, 下面的90题目才需要</span>
        n = len(nums)
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_dfs</span><span class="hljs-params">(start, temp, ans)</span>:</span>
            ans.append(temp)
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(start, n):
                _dfs(i+<span class="hljs-number">1</span>, temp + [nums[i]], ans)
        
        
        _dfs(<span class="hljs-number">0</span>, [], ans)
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<p>二进制法, 总数 2^n,  在范围1~2^n 内，每一个subset正好和一个 数字的二进制对应。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">subsets</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; List[List[int]]:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> nums:
            <span class="hljs-keyword">return</span> []
        n = len(nums)

        ans = []
        <span class="hljs-keyword">for</span> s <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>&lt;&lt;n):
            cur = []
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
                <span class="hljs-keyword">if</span> s &amp; (<span class="hljs-number">1</span>&lt;&lt;i):
                    cur.append(nums[i])
            ans.append(cur)
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<h1 id="2-90-subsets-ii-带有重复元素的全组合可能">2. 90. Subsets II   带有重复元素的全组合可能</h1>
<p>Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).</p>
<p>Note: The solution set must not contain duplicate subsets.</p>
<pre><code><code><div>Example:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]
</div></code></code></pre>
<p>比较好的解法, 但是不容易想到</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">subsetsWithDup</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; List[List[int]]:</span>
        <span class="hljs-comment"># if nums[i] is same to nums[i - 1], then it needn't to be added to all of the subset, </span>
        <span class="hljs-comment"># just add it to the last l subsets which are created by adding S[i - 1]</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> nums:
            <span class="hljs-keyword">return</span> []
        nums.sort()
        res, cur = [[]], []
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(nums)):
            <span class="hljs-keyword">if</span> i &gt; <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> nums[i] == nums[i<span class="hljs-number">-1</span>]:
                cur = [item + [nums[i]] <span class="hljs-keyword">for</span> item <span class="hljs-keyword">in</span> cur]
            <span class="hljs-keyword">else</span>:
                cur = [item + [nums[i]] <span class="hljs-keyword">for</span> item <span class="hljs-keyword">in</span> res]
            res += cur
            print(<span class="hljs-string">f"<span class="hljs-subst">{i}</span> <span class="hljs-subst">{cur}</span> <span class="hljs-subst">{res}</span>"</span>)
        <span class="hljs-keyword">return</span> res
</div></code></pre>
<p>下面是比较容易想到的一个算法。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">subsetsWithDup</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; List[List[int]]:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> nums:
            <span class="hljs-keyword">return</span> []
        
        ans = []
        nums.sort()
        n = len(nums)
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_dfs</span><span class="hljs-params">(start, temp, ans)</span>:</span>
            ans.append(temp)
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(start, n):
                <span class="hljs-keyword">if</span> i == start <span class="hljs-keyword">or</span> (i &gt; start <span class="hljs-keyword">and</span> nums[i] != nums[i<span class="hljs-number">-1</span>]):
                    _dfs(i+<span class="hljs-number">1</span>, temp + [nums[i]], ans)
        
        
        _dfs(<span class="hljs-number">0</span>, [], ans)
        <span class="hljs-keyword">return</span> ans
</div></code></pre>

    </body>
    </html>